package com.zhangxiaofanfan.hotcode.fourth.third;


/**
 * <a href="https://leetcode.cn/problems/search-a-2d-matrix/?envType=study-plan-v2&envId=top-100-liked">74. 搜索二维矩阵</a>
 *
 * @date 2024-06-29 10:22:11
 * @author zhangxiaofanfan
 */
public class HotCode064 {
    public static void main(String[] args) {
        HotCode064 hotCode = new HotCode064();

    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length, col = matrix[0].length, left = 0, right = row * col - 1, mid, rowIndex, colIndex;
        if (target < matrix[0][0] || target > matrix[row - 1][col - 1]) {
            return false;
        }
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            rowIndex = mid / col;
            colIndex = mid % col;
            if (matrix[rowIndex][colIndex] == target) {
                return true;
            } else if (matrix[rowIndex][colIndex] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}
